#region

using System.Text;

#endregion

namespace AdvancedTraining.Lesson40;

/// <summary>
/// 拼出最大能被3整除的数字
/// </summary>
/// <remarks>
/// 来自去哪儿网
/// 给定一个arr，里面的数字都是0~9
/// 你可以随意使用arr中的数字，哪怕打乱顺序也行
/// 请拼出一个能被3整除的，最大的数字，用str形式返回
///
/// 算法思路：
/// 提供三种解法：
/// 1. 暴力递归 + TreeSet：尝试所有可能的组合，选出最大的能被3整除的数字
/// 2. 递归优化：使用记忆化递归，在递归过程中传递余数信息
/// 3. 贪心算法：基于余数分析的贪心策略
///
/// 时间复杂度：
/// - 方法一：O(2^N * logM)，其中M是组合数
/// - 方法二：O(N * 3)，因为余数只有0、1、2三种状态
/// - 方法三：O(N log N)，主要是排序的时间
///
/// 空间复杂度：
/// - 方法一：O(M)，存储所有有效组合
/// - 方法二：O(N)，递归调用栈
/// - 方法三：O(N)，存储排序后的数组
/// </remarks>
public class Mod3Max
{
    /// <summary>
    /// 方法一：暴力递归 + TreeSet
    /// </summary>
    /// <param name="arr">输入数组</param>
    /// <returns>最大能被3整除的数字字符串</returns>
    public static string Max1(int[] arr)
    {
        Array.Sort(arr);
        // 降序排列
        for (int l = 0, r = arr.Length - 1; l < r; l++, r--)
        {
            (arr[l], arr[r]) = (arr[r], arr[l]);
        }

        var builder = new StringBuilder();
        var set = new SortedSet<string>(new StringComparer());
        Process1(arr, 0, builder, set);
        return set.Count == 0 ? "" : set.Min;
    }

    /// <summary>
    /// 方法二：递归优化
    /// </summary>
    /// <param name="arr">输入数组</param>
    /// <returns>最大能被3整除的数字字符串</returns>
    public static string Max2(int[] arr)
    {
        if (arr == null || arr.Length == 0)
            return "";

        Array.Sort(arr);
        // 降序排列
        for (int l = 0, r = arr.Length - 1; l < r; l++, r--)
        {
            (arr[l], arr[r]) = (arr[r], arr[l]);
        }

        if (arr[0] == 0)
            return "0";

        var ans = Process2(arr, 0, 0);
        var res = System.Text.RegularExpressions.Regex.Replace(ans, "^(0+)", "");
        if (!res.Equals(""))
            return res;

        return ans.Equals("") ? ans : "0";
    }

    /// <summary>
    /// 方法三：贪心算法
    /// </summary>
    /// <param name="a">输入数组</param>
    /// <returns>最大能被3整除的数字字符串</returns>
    public static string Max3(int[] a)
    {
        if (a == null || a.Length == 0)
            return "";

        int mod = 0;
        var arr = new List<int>();
        foreach (int num in a)
        {
            arr.Add(num);
            mod += num;
            mod %= 3;
        }

        if ((mod == 1 || mod == 2) && !Remove(arr, mod, 3 - mod))
            return "";

        if (arr.Count == 0)
            return "";

        arr.Sort((x, y) => y - x);
        if (arr[0] == 0)
            return "0";

        var builder = new StringBuilder();
        foreach (int num in arr)
            builder.Append(num);

        return builder.ToString();
    }

    /// <summary>
    /// 暴力递归方法
    /// </summary>
    private static void Process1(int[] arr, int index, StringBuilder builder, SortedSet<string> set)
    {
        if (index == arr.Length)
        {
            if (builder.Length != 0 && int.Parse(builder.ToString()) % 3 == 0)
                set.Add(builder.ToString());
        }
        else
        {
            // 不选择当前数字
            Process1(arr, index + 1, builder, set);
            // 选择当前数字
            builder.Append(arr[index]);
            Process1(arr, index + 1, builder, set);
            builder.Remove(builder.Length - 1, 1);
        }
    }

    /// <summary>
    /// arr中的数字一定是0~9
    /// arr是经过排序的，并且是从大到小排序，比如[9,8,7,7,7,3,1]等
    /// 这个递归函数的含义 :
    /// 在arr[index...一直到最后]上做选择，arr[0...index-1]就当不存在
    /// 每个位置的字符可以要、也可以不要，但是！选出来的数字拼完之后的结果，在%3之后，余数一定要是mod！
    /// 返回在上面设定的情况下，最大的数是多少？
    /// 如果存在这样的数，返回字符串的形式
    /// 如果不存在这样的数，返回特殊字符串，比如"$"，代表不可能
    /// 这个递归函数可以很轻易的改出动态规划
    /// </summary>
    private static string Process2(int[] arr, int index, int mod)
    {
        if (index == arr.Length)
            return mod == 0 ? "" : "$";

        string p1 = "$";
        int nextMod = NextMod(mod, arr[index] % 3);
        string next = Process2(arr, index + 1, nextMod);
        if (!next.Equals("$"))
            p1 = arr[index] + next;

        string p2 = Process2(arr, index + 1, mod);
        if (p1.Equals("$") && p2.Equals("$"))
            return "$";

        if (!p1.Equals("$") && !p2.Equals("$"))
            return Smaller(p1, p2) ? p2 : p1;

        return p1.Equals("$") ? p2 : p1;
    }

    /// <summary>
    /// 计算下一个余数
    /// </summary>
    private static int NextMod(int require, int current)
    {
        if (require == 0)
        {
            if (current == 0)
                return 0;
            if (current == 1)
                return 2;
            return 1;
        }

        if (require == 1)
        {
            if (current == 0)
                return 1;
            if (current == 1)
                return 0;
            return 2;
        }

        // require == 2
        if (current == 0)
            return 2;
        if (current == 1)
            return 1;
        return 0;
    }

    /// <summary>
    /// 比较两个字符串的大小
    /// </summary>
    private static bool Smaller(string p1, string p2)
    {
        if (p1.Length != p2.Length)
            return p1.Length < p2.Length;

        return string.Compare(p1, p2, StringComparison.Ordinal) < 0;
    }

    /// <summary>
    /// 贪心的思路解法 :
    /// 先得到数组的累加和，记为sum
    /// 1) 如果sum%3==0，说明所有数从大到小拼起来就可以了
    /// 2) 如果sum%3==1，说明多了一个余数1，
    /// 只需要删掉一个最小的数(该数是%3==1的数);
    /// 如果没有，只需要删掉两个最小的数(这两个数都是%3==2的数);
    /// 3) 如果sum%3==2，说明多了一个余数2，
    /// 只需要删掉一个最小的数(该数是%3==2的数);
    /// 如果没有，只需要删掉两个最小的数(这两个数都是%3==1的数);
    /// 如果上面都做不到，说明拼不成
    /// </summary>
    /// <param name="arr">数组</param>
    /// <param name="first">第一个余数</param>
    /// <param name="second">第二个余数</param>
    /// <returns>是否能删除满足条件的数</returns>
    private static bool Remove(List<int> arr, int first, int second)
    {
        if (arr.Count == 0)
            return false;

        arr.Sort((a, b) => Compare(a, b, first, second));
        int size = arr.Count;
        if (arr[size - 1] % 3 == first)
        {
            arr.RemoveAt(size - 1);
            return true;
        }

        if (size > 1 && arr[size - 1] % 3 == second && arr[size - 2] % 3 == second)
        {
            arr.RemoveAt(size - 1);
            arr.RemoveAt(size - 2);
            return true;
        }

        return false;
    }

    /// <summary>
    /// a和b比较：
    /// 如果余数一样，谁大谁放前面
    /// 如果余数不一样，余数是0的放最前面、余数是s的放中间、余数是f的放最后
    /// </summary>
    private static int Compare(int a, int b, int f, int s)
    {
        int ma = a % 3;
        int mb = b % 3;
        if (ma == mb)
            return b - a;

        if (ma == 0 || mb == 0)
            return ma == 0 ? -1 : 1;
        return ma == s ? -1 : 1;
    }

    /// <summary>
    /// 字符串比较器，用于降序排列
    /// </summary>
    private class StringComparer : IComparer<string>
    {
        public int Compare(string? a, string? b)
        {
            if (a == null && b == null) return 0;
            if (a == null) return 1;
            if (b == null) return -1;
            return int.Parse(b).CompareTo(int.Parse(a));
        }
    }

    /// <summary>
    /// 为了测试，生成随机数组
    /// </summary>
    private static int[] RandomArray(int len)
    {
        var arr = new int[len];
        var random = new Random();
        for (var i = 0; i < len; i++)
            arr[i] = random.Next(10);

        return arr;
    }

    /// <summary>
    /// 为了测试，复制数组
    /// </summary>
    private static int[] CopyArray(int[] arr)
    {
        var ans = new int[arr.Length];
        for (var i = 0; i < arr.Length; i++)
            ans[i] = arr[i];

        return ans;
    }

    /// <summary>
    /// 运行测试用例
    /// </summary>
    public static void Run()
    {
        Console.WriteLine("=== Mod3Max 测试 ===");

        // 测试用例1：基本测试
        var arr1 = new int[] { 8, 1, 9 };
        Console.WriteLine($"测试1 - 基本数组: [{string.Join(",", arr1)}]");
        Console.WriteLine($"方法一结果: {Max1(CopyArray(arr1))}");
        Console.WriteLine($"方法二结果: {Max2(CopyArray(arr1))}");
        Console.WriteLine($"方法三结果: {Max3(CopyArray(arr1))}");
        Console.WriteLine();

        // 测试用例2：全是0
        var arr2 = new int[] { 0, 0, 0 };
        Console.WriteLine($"测试2 - 全是0: [{string.Join(",", arr2)}]");
        Console.WriteLine($"方法一结果: {Max1(CopyArray(arr2))}");
        Console.WriteLine($"方法二结果: {Max2(CopyArray(arr2))}");
        Console.WriteLine($"方法三结果: {Max3(CopyArray(arr2))}");
        Console.WriteLine();

        // 测试用例3：不能被3整除
        var arr3 = new int[] { 8, 1 };
        Console.WriteLine($"测试3 - 不能被3整除: [{string.Join(",", arr3)}]");
        Console.WriteLine($"方法一结果: {Max1(CopyArray(arr3))}");
        Console.WriteLine($"方法二结果: {Max2(CopyArray(arr3))}");
        Console.WriteLine($"方法三结果: {Max3(CopyArray(arr3))}");
        Console.WriteLine();

        // 测试用例4：空数组
        var arr4 = new int[] { };
        Console.WriteLine($"测试4 - 空数组: [{string.Join(",", arr4)}]");
        Console.WriteLine($"方法一结果: '{Max1(arr4)}'");
        Console.WriteLine($"方法二结果: '{Max2(arr4)}'");
        Console.WriteLine($"方法三结果: '{Max3(arr4)}'");
        Console.WriteLine();

        // 测试用例5：复杂情况
        var arr5 = new int[] { 5, 2, 2 };
        Console.WriteLine($"测试5 - 复杂情况: [{string.Join(",", arr5)}]");
        Console.WriteLine($"方法一结果: {Max1(CopyArray(arr5))}");
        Console.WriteLine($"方法二结果: {Max2(CopyArray(arr5))}");
        Console.WriteLine($"方法三结果: {Max3(CopyArray(arr5))}");
        Console.WriteLine();

        Console.WriteLine("=== 性能测试开始 ===");
        PerformanceTest();
        Console.WriteLine("=== 性能测试结束 ===");

        Console.WriteLine("=== 测试完成 ===");
    }

    /// <summary>
    /// 性能测试，验证三种方法结果一致性
    /// </summary>
    private static void PerformanceTest()
    {
        const int N = 10;
        const int testTimes = 10000;
        Console.WriteLine($"开始性能测试，测试次数: {testTimes}");

        for (var i = 0; i < testTimes; i++)
        {
            var len = new Random().Next(N);
            var arr1 = RandomArray(len);
            var arr2 = CopyArray(arr1);
            var arr3 = CopyArray(arr1);

            var ans1 = Max1(arr1);
            var ans2 = Max2(arr2);
            var ans3 = Max3(arr3);

            if (ans1 != null && (!ans1.Equals(ans2) || !ans1.Equals(ans3)))
            {
                Console.WriteLine("发现不一致的结果！");
                Console.WriteLine($"原始数组: [{string.Join(",", arr3)}]");
                Console.WriteLine($"方法一: {ans1}");
                Console.WriteLine($"方法二: {ans2}");
                Console.WriteLine($"方法三: {ans3}");
                break;
            }
        }

        Console.WriteLine("所有测试通过，三种方法结果一致！");
    }
}